package leetcode101.data_structure;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Synhard
 * @version 1.0
 * @class Code18
 * @description 560. 和为K的子数组
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 * 示例 1 :
 *
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-16 9:11
 */
public class Code18 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1};
        System.out.println(subarraySum(nums, 2));
    }

    public static int subarraySum(int[] nums, int k) {
        int n = nums.length, res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        for (int i : prefix) {
            if (map.get(i - k) != null) {
                res += map.get(i - k);
            }
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        return res;
    }
}

/*
使用前缀和
构建HashMap
key 为对应的前缀和， value为前缀和的个数
遍历构建好的prefix数组
对于prefix[i] res += map.get(prefix[i] - k)
并且要更新map，因为加入了新的元素
map.put(prefix[i], map.getOrDefault(prefix[i], 0) + 1);
 */